package leetcode_81_100;

import utils.TreeNode;

public class recoverTree_99 {
    /**
     * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。
     * 请在不改变其结构的情况下，恢复这棵树 。
     * @param root
     */
    public void recoverTree(TreeNode root) {
        recoverBTS(root);
        //如果x和y都不为空，说明二叉搜索树出现错误的节点，将其交换
        if(x!=null && y!=null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }
    //用两个变量x，y来记录需要交换的节点
    private TreeNode x = null;
    private TreeNode y = null;
    private TreeNode pre = null;
    /**
     * 想法是通过中序遍历
     * 可能有两个位置发现错误。
     * 只有一个位置错误的话就是一开始的xy，
     * 两位置错误的话就是第一个位置的第一个元素x和第二个位置的第2个元素（新的y）交换。
     */
    public void recoverBTS(TreeNode root) {
        if (root == null) return;
        //进入左节点
        recoverBTS(root.left);

        //前一个节点为null
        if(pre==null) {
            pre = root;
        }
        else {    //否则进行判断
            if(pre.val>root.val) { //前一个节点大于当前节点
                y = root;       //将每次出问题的两个节点的后一个进行赋值给y
                if(x==null) { //x只赋值一次，即第一次问题的两个节点的前一个
                    x = pre;
                }
            }
            pre = root;
        }
        //进入右节点
        recoverBTS(root.right);
    }

}
